package trie

import (
//"fmt"
//"strings"
)

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

type Trie struct {
	root *TrieNode
}

func NewTrieNode() *TrieNode {
	return &TrieNode{
		children: make(map[rune]*TrieNode),
	}
}

func NewTrie() *Trie {
	return &Trie{
		root: NewTrieNode(),
	}
}

func (t *Trie) AddWord(word string) {
	node := t.root
	for _, c := range word {
		if _, ok := node.children[c]; !ok {
			node.children[c] = NewTrieNode()
		}
		node = node.children[c]
	}
	node.isEnd = true
}

func (t *Trie) isMatch(text []rune) (int, bool) {
	find := false
	var length int
	node := t.root
	for i, ch := range text {
		child, ok := node.children[ch]
		if !ok {
			return length, find
		}
		node = child
		if node.isEnd {
			find = true
			length = i + 1
		}
	}

	return length, find
}

func (t *Trie) Replace(text []rune, replace rune) string {
	res := text
	for i := 0; i < len(text); {
		length, ok := t.isMatch(text[i:])
		if !ok {
			i++
			continue
		}
		for j := i; j < i+length; j++ {
			res[j] = replace
		}
		i += length
	}
	return string(res)
}

//func main() {
//trie := NewTrie()
//trie.AddWord("中国")
//trie.AddWord("中国人")
//trie.AddWord("中国小说网")
//fmt.Println("res:", trie.Replace("我是中国人民共和国公民", '*'))
//}
